|
The Abelian sandpile model, also known as the Bak–Tang–Wiesenfeld model, was the first discovered example of a dynamical system displaying self-organized criticality. It was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper.〔 〕 The model is a cellular automaton. In its original formulation, each site on a finite grid has an associated value that corresponds to the slope of the pile. This slope builds up as grains of sand are randomly placed onto the pile, until the slope exceeds a specific threshold value at which time that site collapses transferring sand into the adjacent sites, increasing their slope. Bak, Tang, and Wiesenfeld considered process of successive random placement of sand grains on the grid; each such placement of sand at a particular site may have no effect, or it may cause a cascading reaction that will affect many sites. The grains of sand are often more conveniently referred to as "chips". The model has since been studied on the infinite lattice, on other (non-square) lattices, and on arbitrary graphs (including directed multigraphs). ==Definition== The iteration rules for the model on the square lattice can be defined as follows: Begin with some nonnegative configuration which is finite, in the sense that :. Any site with : is ''unstable'' and can ''topple'', sending one of its chips to each of its 4 neighbors: : : : The process is guaranteed to terminate given that the initial configuration was finite. Moreover, although there will often be many possible choices for the order in which to topple vertices, the final configuration does not depend on the chosen order; this is one sense in which the sandpile is ''Abelian''. The number of times each vertex topples in this process is also independent of the choice of toppling order. On an arbitrary undirected graph, a special vertex called a ''sink'' is specified that is not allowed to topple. In the presence of a sink, the term ''chip configuration'' refers to a chip-counting vector (nonnegative and integral) indexed by the non-sink vertices. The rules are that any non-sink vertex with : is unstable; toppling again sends one of its chips to each of its neighbors: : and, for each : : Multiple toppling operations can be efficiently encoded by using the Laplacian matrix . Deleting the row and column of corresponding with the sink yields the ''reduced Laplacian'' . If is a nonnegative integral vector indexed by the non-sink vertices, then starting with a configuration and toppling each vertex a total of times yields the configuration . This and other models that involve a toppling operation are sometimes referred to as ''chip-firing models'' or ''chip-firing games''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Abelian sandpile model」の詳細全文を読む スポンサード リンク
|